1. Field of the Invention
This invention relates generally to video encoding/decoding methods and more particularly to video encoding/decoding methods for use in conjunction with low bandwidth connections and low performance devices.
2. Description of the Related Art
Video streams are regularly encoded, transmitted over computer networks, and decoded and displayed on desktop computers. Web browsers and the World Wide Web have facilitated access to and presentation of video media. The recent combination of the palmtop computing device and wireless access to the Internet has provided a basic platform for wireless web browsing. Lower bandwidths and processing performances, however, make conventional encoding and streaming techniques inapplicable for streaming video to wirelessly connected palmtop devices.
State of the art video compression standards such as H.261, H.263, MPEG1/2/4 and M-JPEG are based on either Discrete Cosine Transform (DCT) or Wavelet Transformation. Prototype implementations with H.263 and a Custom DCT codec have shown that the DCT decoding process is too slow on current Palm Operating System (“PalmOS”) platforms. The same holds for the Wavelet transformations. A principal reason for this is the large number of multiplications required for decoding. Typical implementations use the Chen-Wang algorithm (IEEE ASSP-32, pp. 803–816, August 1984). In the worst case, this algorithm requires 176 multiplications and 464 adds per 8×8 pixel block. A typical PalmOS device has a 160×160 pixel frame, in which case 70,400 multiplications are needed. A 68000 series microprocessor needs roughly 80 cycles for a single multiplication. Thus, a microprocessor running at 20 MHz takes approximately 0.28 seconds to perform these multiplications, leading to a frame rate about 3 frames per second. This calculation, however, assumes the worst case. Higher frame rates may be theoretically achieved by reducing the video frame size, limiting the number of colors, and/or reducing the video quality by means of DCT vector quantisation. Shortcuts in the Chen-Wang algorithm can benefit from vectors that equal zero. Nevertheless, the given approximation of the decoding delay does not include the adds and the additional DCT vectors needed for color videos. Prototype implementations have shown that the decoding delay for a full screen video frame in photo quality is at least 1.5 seconds.
In general, a more realistic solution for very low-performance client devices is block-based difference encoding, because of its low computing demands on the decoding client device. However, it is generally accepted by those skilled in art that the central challenge in such algorithms is to select an optimal encoding block size. Quoting from New Media Republic's description of interface video encoding (see article http://www.newmediarepublic.com/dvideo/compression/adv07.html, by Collin Manning, lecturer in computer science at Cork Institute of Technology, included herein as an exhibit), ‘Clearly the choice of block size must be an informed one so as to achieve the best balance between image quality and cession.’
Please note that block-based motion compensation is an entirely different category of video compression from block-based difference encoding. Motion compensation has little relevance under low-performance computing conditions, because the client-side vector algebra required for computing image region translations based on arbitrary vectors is too multiplication-intensive for low performance client devices. As a result, inventions such as Krause (U.S. Pat. No. 5,235,419) cannot be applied under these conditions, nor can they be modified to resemble block-based difference encoding methods.
For a succinct description of the differences between block-based difference coding and block-based motion compensation, refer to the aforementioned Manning article.
The embodiments of the invention seek to provide video encoding techniques and formats that are well-suited to decoding by low-performance devices, such as a PalmOS device, and that is well-suited to transmission over low-bandwidth links, such as wireless networks.